#include <iostream>
#include <stack>


struct Node {
    int val;
    Node *left;
    Node *right;
};

void pre_order1(Node *root)
{
    if (root != NULL) {
        std::cout << root->val << " ";
        pre_order1(root->left);
        pre_order1(root->right);
    }
}

void pre_order2(Node *root)
{
    std::stack<Node *> s;
    Node *t = root;

    while (t != NULL || !s.empty()) {
        if (t != NULL) {
            std::cout << t->val << " ";
            s.push(t);
            t = t->left;
        } else {
            t = s.top();
            s.pop();
            t = t->right;
        }
    }
}

void link(Node nodes[], int t, int l, int r)
{
    if (l != -1) {
        nodes[t].left = &nodes[l];
    }

    if (r != -1) {
        nodes[t].right = &nodes[r];
    }
}

int main(int argc, const char *argv[])
{
    Node nodes[] = {
        {1, NULL, NULL},
        {2, NULL, NULL},
        {3, NULL, NULL},
        {4, NULL, NULL},
        {5, NULL, NULL},
        {6, NULL, NULL},
        {7, NULL, NULL}
    };

    link(nodes, 0, 1, 2);
    link(nodes, 1, 3, 4);
    link(nodes, 2, 5, 6);

    pre_order1(nodes);
    std::cout << std::endl;
    pre_order2(nodes);
    return 0;
}
